#include "my_string.h"
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

/* 参考模式串pattern: abcabcmn */
vector<int> StringOperation::get_next(const string &pattern)
{
    cout << "Use base method to create next array" << endl;
    auto size = pattern.size();
    vector<int> next_array(size, 0);
    next_array[0] = -1;
    /* j 用来表示字符串尾部的下标 */
    /* k 用来表示字符串头部的下标 */
    decltype(pattern.size()) j = 0;
    decltype(pattern.size()) k = -1;

    while (j < size - 1) {
        /* k==-1，表示在字符串下标为0的前面，一个不存在的虚拟下标 */
        /* k==-1，即表示下标index为0的字符，也无法匹配上 */
        if (k == -1 || pattern[k] == pattern[j]) {
            /* 前后的字符相等，则k和j均+1 */
            ++k;
            ++j;
            /* 在j和k均没有+1之前，要么k为-1，要么两个字符相等 */
            /* 1. 如果k为-1，则下标为j的字符匹配失败的时候，只能从头开始匹配了
             */
            /* 如果是前后两个字符相等，则当前位置匹配失败时，下一个开始的位置从k开始
             */
            next_array[j] = k;
        } else {
            /* 如果当前的字符pattern[i]和pattern[k]不相等，则将k变成其next数组中的下一个位置，继续与pattern[j]进行匹配
             */
            k = next_array[k];
        }
    }

    return next_array;
}

vector<int> AdvancedKmpMethod::get_next(const std::string &pattern)
{
    cout << "Use optimized method to create next array" << endl;
    auto size = pattern.size();
    vector<int> next_array(size, 0);
    next_array[0] = -1;
    decltype(pattern.size()) j = 0;
    decltype(pattern.size()) k = -1;

    while (j < size - 1) {
        if (k == -1 || pattern[k] == pattern[j]) {
            ++k;
            ++j;
            if (next_array[k] == pattern[j]) {
                next_array[j] = next_array[k];
            } else {
                next_array[j] = k;
            }
        } else {
            k = next_array[k];
        }
    }

    return next_array;
}

int StringOperation::kmp(const std::string &str, const std::string &pattern)
{
    vector<int> next_array = this->get_next(pattern);
    decltype(str.size()) str_size = str.size();
    decltype(pattern.size()) pattern_size = pattern.size();
    decltype(str.size()) i = 0;
    decltype(pattern.size()) j = -1;

    while (i < str_size) {
        if (j == -1 || str[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next_array[j];
        }
        if (j == pattern_size - 1) {
            cout << "string: " << str << " pattern: " << pattern
                 << " index: " << (i - j) << endl;
            return (i - j);
        }
    }

    cout << "string: " << str << " pattern: " << pattern << " index: " << (-1)
         << endl;
    return -1;
}

int main()
{
    StringOperation *str_op = new StringOperation;
    AdvancedKmpMethod *str_adv = new AdvancedKmpMethod;
    string str = "abcabeabcabcmn";
    string pattern = "abcabcmn";

    str_op->kmp(str, pattern);
    str_op = str_adv;
    str_op->kmp(str, pattern);
}